package link;

/*
*
* 给定一个链表，每个节点包含一个额外增加的随机指针，该指针可以指向链表中的任何节点或空节点。

要求返回这个链表的深拷贝。 

 

示例：



输入：
{"$id":"1","next":{"$id":"2","next":null,"random":{"$ref":"2"},"val":2},"random":{"$ref":"2"},"val":1}

解释：
节点 1 的值是 1，它的下一个指针和随机指针都指向节点 2 。
节点 2 的值是 2，它的下一个指针指向 null，随机指针指向它自己。
 

提示：

你必须返回给定头的拷贝作为对克隆列表的引用。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/copy-list-with-random-pointer
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
* */

public class CopyRandomList {

    class Node {
        int val;
        Node next;
        Node random;

        public Node(int val) {
            this.val = val;
            this.next = null;
            this.random = null;
        }

    }

    public Node copyRandomList(Node head) {
        if(head == null){
            return null;
        }

        Node copyHead = new Node(head.val);
        copyHead.next = head.next;
        Node copyNode = null;
        Node node = copyHead.next;
        while(node != null){
            copyNode = new Node(node.val);
            copyNode.next = node.next;
            node.next = copyNode;
            node = copyNode.next;
        }
        node = head;
        while(node != null){
            copyNode = node.next;
            if(node.random != null){
                copyNode.random = node.random.next;
            }
            node = copyNode.next;
        }

        node = head;
        copyNode = copyHead;
        while(copyNode.next != null){
            Node temp = copyNode.next;
            copyNode.next = temp.next;
            node.next = temp;
            node = node.next;
            copyNode = copyNode.next;
        }
        node.next = null;
        return copyHead;
    }
}
